home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 11 - 1995 / 11.05 May 95 / dispatch.c < prev   
Encoding:
C/C++ Source or Header  |  1995-03-12  |  9.4 KB  |  307 lines  |  [TEXT/KAHL]
  1.  
  2. /* dispatch.c */
  3. /* Copyright (C) 1995 Gustav K. Larsson */
  4.  
  5. /* ====================================================== */
  6.  
  7. #define kMethodNotFound ((void *) 0)
  8. #define kClassNotFound  ((void *) -1)
  9.  
  10. typedef unsigned char uchar;
  11. typedef unsigned short ushort;
  12. typedef unsigned long ulong;
  13.  
  14. typedef ushort  ClassID;
  15. typedef ushort  MethodNumber;
  16. typedef void *  MethodAddress;
  17.  
  18. typedef struct {
  19.   MethodNumber  methodNumber;
  20.   MethodAddress methodAddress;
  21. } MethodEntry;
  22.  
  23. typedef struct {
  24.   ushort        inheritedCount;
  25.   ushort        inheritedClasses[15];
  26.   MethodNumber  largestMethodNumber;
  27.   ushort        methodCount;
  28.   MethodEntry   methods[];
  29. } Class, *ClassPtr;
  30.  
  31. /* ====================================================== */
  32.  
  33. /*
  34.  * Each block in the cache is 64 bytes and holds 10 entries.
  35.  * The id field distinguishes class/method pairs that map to
  36.  * the same cache block. The hits field has a bit for each
  37.  * entry, which is set whenever there is a hit on the entry.
  38.  * The "next" field is 0..9 and indicates where to check
  39.  * first when deciding which entry to replace.
  40.  */
  41.  
  42. #define BLOCK_SIZE 10
  43.  
  44. typedef struct {
  45.   ushort          id [ BLOCK_SIZE ];
  46.   ushort          hits;
  47.   ushort          next;
  48.   MethodAddress   methodAddress [ BLOCK_SIZE ];
  49. } CacheBlock;
  50.  
  51. static CacheBlock Cache[256]; /* exactly 16K */
  52.  
  53. /* ====================================================== */
  54.  
  55. extern ClassPtr GetClassPtr( ClassID );
  56. MethodAddress FindMethod( ClassID, MethodNumber );
  57. static MethodAddress HandleMiss( ClassID, MethodNumber,
  58.                                  CacheBlock *, ushort );
  59.  
  60. /* ====================================================== */
  61.  
  62. MethodAddress
  63. FindMethod( ClassID classID, MethodNumber methodNumber )
  64. {
  65.   register ulong hash;
  66.   register ushort *idPtr;
  67.   register CacheBlock *block;
  68.  
  69.   /*
  70.    * Check cache for this class & method.
  71.    *
  72.    * First, generate a hash key that is unique for each
  73.    * class/method pair. The formula classID + 437 * method
  74.    * works since 437 is greater than the highest class ID,
  75.    * 400. The ideal multiplier depends heavily on the
  76.    * distribution of class/method pairs, but 437 seems to
  77.    * give a reasonable spread under a variety of conditions.
  78.    *
  79.    * The low byte of the hash key becomes the block number,
  80.    * and the higher bytes become the "id" (to distinguish
  81.    * class/method pairs that map to the same block). Add one
  82.    * to the id so it is never zero (zero indicates an unused
  83.    * cache entry).
  84.    */
  85.  
  86.   hash = classID + 437L * methodNumber;
  87.   block = &Cache[ (uchar)hash ];
  88.   hash = (hash >> 8) + 1;   /* now hash holds just the id */
  89.  
  90.   idPtr = block->id;
  91.   if ( *idPtr++ == (ushort)hash ) goto hit0;
  92.   if ( *idPtr++ == (ushort)hash ) goto hit1;
  93.   if ( *idPtr++ == (ushort)hash ) goto hit2;
  94.   if ( *idPtr++ == (ushort)hash ) goto hit3;
  95.   if ( *idPtr++ == (ushort)hash ) goto hit4;
  96.   if ( *idPtr++ == (ushort)hash ) goto hit5;
  97.   if ( *idPtr++ == (ushort)hash ) goto hit6;
  98.   if ( *idPtr++ == (ushort)hash ) goto hit7;
  99.   if ( *idPtr++ == (ushort)hash ) goto hit8;
  100.   if ( *idPtr++ == (ushort)hash ) goto hit9;
  101.  
  102.   return HandleMiss( classID, methodNumber,
  103.                      block, (ushort)hash );
  104.  
  105.   /* Handle cache hit */
  106.  
  107. hit0: block->hits |= 0x001;  return block->methodAddress[0];
  108. hit1: block->hits |= 0x002;  return block->methodAddress[1];
  109. hit2: block->hits |= 0x004;  return block->methodAddress[2];
  110. hit3: block->hits |= 0x008;  return block->methodAddress[3];
  111. hit4: block->hits |= 0x010;  return block->methodAddress[4];
  112. hit5: block->hits |= 0x020;  return block->methodAddress[5];
  113. hit6: block->hits |= 0x040;  return block->methodAddress[6];
  114. hit7: block->hits |= 0x080;  return block->methodAddress[7];
  115. hit8: block->hits |= 0x100;  return block->methodAddress[8];
  116. hit9: block->hits |= 0x200;  return block->methodAddress[9];
  117.  
  118. }
  119.  
  120. /* ====================================================== */
  121.  
  122. static MethodAddress
  123. HandleMiss( ClassID classID, MethodNumber methodNumber,
  124.             CacheBlock *blockPtr, ushort id )
  125. {
  126.   register ClassPtr classPtr;
  127.   MethodAddress methodAddress;
  128.   register ushort *temp;  /* shared address register */
  129.  
  130.   /* Not in cache, so look it up the hard way */
  131.  
  132.   classPtr = GetClassPtr( classID );
  133.   if ( classPtr != kClassNotFound ) {
  134.  
  135.     /* Look in this class. Use a binary search. */
  136.  
  137.     {
  138.       register MethodEntry *methods = classPtr->methods;
  139.       ushort searchSize = classPtr->methodCount;
  140.       register MethodNumber methodReg = methodNumber;
  141.                                 /* method # in a register */
  142.  
  143.     /*
  144.      * Unroll the binary search for the most common cases.
  145.      * The BINARY macro reduces the search to progressively
  146.      * more elementary cases. If classPtr->methodCount is
  147.      * greater than 32, then we run a general binary search
  148.      * until the search is reduced to an unrolled case.
  149.      */
  150.  
  151. continueBinarySearch:
  152.       switch ( searchSize )
  153.       {
  154.         bin2: case 2:
  155.           if ( methods[1].methodNumber == methodReg ) {
  156.             methodAddress = methods[1].methodAddress;
  157.             goto addCache;
  158.           }
  159.           /* else fall through... */
  160.         bin1: case 1:
  161.           if ( methods[0].methodNumber == methodReg ) {
  162.             methodAddress = methods[0].methodAddress;
  163.             goto addCache;
  164.           }
  165.           else goto checkSuperclasses;
  166.  
  167.       #define BINARY(mid,mid1)                        \
  168.         if ( methodReg < methods[mid].methodNumber )  \
  169.           goto bin##mid;  /* like "hi = mid" */       \
  170.         else {                                        \
  171.           methods += mid; /* like "lo = mid" */       \
  172.           goto bin##mid1;                             \
  173.         }
  174.  
  175.         /* binN: case N: BINARY(N/2,(N+1)/2) */
  176.         bin3:  case  3: BINARY(1,2)
  177.         bin4:  case  4: BINARY(2,2)
  178.         bin5:  case  5: BINARY(2,3)
  179.         bin6:  case  6: BINARY(3,3)
  180.         bin7:  case  7: BINARY(3,4)
  181.         bin8:  case  8: BINARY(4,4)
  182.         bin9:  case  9: BINARY(4,5)
  183.         bin10: case 10: BINARY(5,5)
  184.         bin11: case 11: BINARY(5,6)
  185.         bin12: case 12: BINARY(6,6)
  186.         bin13: case 13: BINARY(6,7)
  187.         bin14: case 14: BINARY(7,7)
  188.         bin15: case 15: BINARY(7,8)
  189.         bin16: case 16: BINARY(8,8)
  190.         bin17: case 17: BINARY(8,9)
  191.         bin18: case 18: BINARY(9,9)
  192.         bin19: case 19: BINARY(9,10)
  193.         bin20: case 20: BINARY(10,10)
  194.         bin21: case 21: BINARY(10,11)
  195.         bin22: case 22: BINARY(11,11)
  196.         bin23: case 23: BINARY(11,12)
  197.         bin24: case 24: BINARY(12,12)
  198.         bin25: case 25: BINARY(12,13)
  199.         bin26: case 26: BINARY(13,13)
  200.         bin27: case 27: BINARY(13,14)
  201.         bin28: case 28: BINARY(14,14)
  202.         bin29: case 29: BINARY(14,15)
  203.         bin30: case 30: BINARY(15,15)
  204.         bin31: case 31: BINARY(15,16)
  205.         bin32: case 32: BINARY(16,16)
  206.  
  207.         #define NUM_UNROLLED 32 /* # of unrolled cases */
  208.  
  209.         default:
  210.           if (methodReg <= classPtr->largestMethodNumber) {
  211.             register ushort lo, mid, hi, mn;
  212.             lo = 0;
  213.             hi = classPtr->methodCount - 1;
  214.             while ( lo + NUM_UNROLLED - 1 < hi ) {
  215.               mid = (lo + hi) >> 1;
  216.               mn = methods[mid].methodNumber;
  217.               if ( methodReg < mn )
  218.                 hi = mid;
  219.               else if ( methodReg > mn )
  220.                 lo = mid;
  221.               else {
  222.                 methodAddress = methods[mid].methodAddress;
  223.                 goto addCache;
  224.               }
  225.             }
  226.             /* reduced to an unrolled case */
  227.             searchSize = hi-lo+1;
  228.             methods += lo;
  229.             goto continueBinarySearch;
  230.           }
  231.       }
  232.     }
  233.  
  234.     /*
  235.      * Look in superclasses. Eliminating the recursion by
  236.      * keeping a custom stack of critical variables doesn't
  237.      * buy us much. Recursion also makes the code clearer.
  238.      */
  239.  
  240. checkSuperclasses:
  241.     {
  242.       register ulong i, max = classPtr->inheritedCount;
  243.  
  244.       /* shared address register points into class list */
  245.       temp = classPtr->inheritedClasses;
  246.  
  247.       for ( i = 0; i < max; i++ ) {
  248.         methodAddress = FindMethod(*temp++, methodNumber);
  249.         if ( methodAddress != kMethodNotFound )
  250.           goto addCache;
  251.       }
  252.     }
  253.   }
  254.  
  255.   /*
  256.    * There are two ways to get here: classPtr is
  257.    * kClassNotFound (hopefully rare), or the method was not
  258.    * found in any of the superclasses. Either way, put a
  259.    * "not found" entry into the cache. This helps when
  260.    * searching complicated inheritance hierarchies or
  261.    * repeatedly looking up the same method in several
  262.    * related subclasses.
  263.    */
  264.  
  265.   methodAddress = kMethodNotFound;
  266.  
  267.   /*
  268.    * Add an entry to the cache.
  269.    */
  270.  
  271. addCache:
  272.  
  273.   /* shared address register holds block pointer */
  274.   temp = (ushort*) blockPtr;
  275.   #define block ((CacheBlock*) temp)
  276.  
  277.   {
  278.     register ulong hits = block->hits;
  279.     register ulong next = block->next;
  280.     register ulong mask = 1L << next;
  281.  
  282.     /*
  283.      * Choose the entry to replace. Look for a cleared
  284.      * bit in "hits" starting at "next". If all the bits
  285.      * are 1 initially, go all the way around; we are
  286.      * guaranteed to stop since we clear bits as we go.
  287.      */
  288.  
  289.     while ( hits & mask ) {
  290.       hits &= ~mask;              /* no, clear the bit */
  291.       mask <<= 1;                 /* and try next bit */
  292.       if ( mask == (1 << BLOCK_SIZE) )
  293.         mask = 1;
  294.       next++;
  295.     }
  296.     if ( next >= BLOCK_SIZE )
  297.       next -= BLOCK_SIZE;
  298.  
  299.     block->methodAddress[ next ] = methodAddress;
  300.     block->id[ next ] = id;
  301.     block->hits = hits;
  302.     block->next = ( next < BLOCK_SIZE-1 ? next+1 : 0 );
  303.   }
  304.  
  305.   return methodAddress;
  306. }
  307.